// run: $exec < input
#include <iostream>
#include <iomanip>
#include <utility>
#include <set>
#include <unordered_map>

int const maxn = 4000;
std::unordered_map<int, int> f[maxn][maxn];
std::unordered_map<int, bool> vis[maxn][maxn];
int n, m;

template <class T>
T abs(T x) { if (x < 0) return -x; else return x; }
int gcd(int x, int y) { return !y ? x : gcd(y, x % y); }

int fj_calc(int m, int n, int j)
{
	if (vis[m][n][j]) return f[m][n][j];
	int ret = 0;
	for (int x = -n; x <= n; x++)
		for (int y = -m; y <= m; y++)
			if (gcd(x, y) == j) ret += (n - abs(x)) * (m - abs(y));
	vis[m][n][j] = true;
	return f[m][n][j] = ret;
}

int lj_calc(int m, int n, int j)
{
	int ret = fj_calc(m, n, j + 1) - 2 * fj_calc(m, n, j)
				+ fj_calc(m, n, j - 1);
	return ret;
}

int l_calc(int m, int n)
{
	int ret = 0;
	for (int i = 2; i <= std::max(n, m); i++)
		ret += lj_calc(m, n, i);
	return ret;
}

int main()
{
	std::ios::sync_with_stdio(false);
	int T; std::cin >> T;
	while (T--) {
		std::cin >> n >> m;
		std::cout << l_calc(n, m) << '\n';
	}
}

